package main

type Node struct {
	IsEnd    bool
	children [26]*Node
}

type WordDictionary struct {
	root *Node
}

func Constructor() WordDictionary {
	return WordDictionary{
		root: &Node{},
	}
}

func (this *WordDictionary) AddWord(word string) {
	n := this.root
	for _, c := range word {
		idx := c - 'a'
		if n.children[idx] == nil {
			n.children[idx] = &Node{
				children: [26]*Node{},
			}
		}
		n = n.children[idx]
	}
	n.IsEnd = true
}

func (this *WordDictionary) Search(word string) bool {
	return search(this.root, word)
}

func search(root *Node, word string) bool {
	n := root
	for i, c := range word {
		if c == '.' {
			for _, child := range n.children {
				if child != nil {
					if search(child, word[i+1:]) {
						return true
					}
				}
			}
			return false
		} else {
			idx := c - 'a'
			if n.children[idx] == nil {
				return false
			}
			n = n.children[idx]
		}
	}
	return n.IsEnd
}

func main() {
	//dict := Constructor()
	//	dict.AddWord("bad")
	//	println(dict.Search("bad"))
	//	println(dict.Search("b.d"))
	//	println(dict.Search("ba."))
	//	println(dict.Search("bd."))
	dict := Constructor()
	dict.AddWord("a")
	dict.AddWord("a")
	println(dict.Search("a."))
	println(dict.Search(".a"))
}
